
-- 斐波那契数列性能测试程序

-- 递归实现斐波那契数列
function fib_recursive(n)
    if n <= 1 then
        return n
    end
    return fib_recursive(n-1) + fib_recursive(n-2)
end

-- 迭代实现斐波那契数列
function fib_iterative(n)
    if n <= 1 then
        return n
    end
    local a, b = 0, 1
    for i = 2, n do
        a, b = b, a + b
    end
    return b
end

-- 测量函数执行时间
function measure_time(func, ...)
    local start_time = os.clock()
    local result = func(...)
    local end_time = os.clock()
    return result, end_time - start_time
end

-- 运行性能测试
function run_performance_test(n)
    print("== 斐波那契数列性能测试 ==")
    print(string.format("计算第 %d 个斐波那契数：\n", n))
    
    -- 测试迭代版本
    local iter_result, iter_time = measure_time(fib_iterative, n)
    print(string.format("迭代版本: 结果 = %d, 耗时 = %.6f 秒", iter_result, iter_time))
    
    -- 注意：对于大的n值，递归版本可能会非常慢或导致栈溢出
    -- 这里限制n为较小值以避免性能问题
    if n <= 30 then
        local rec_result, rec_time = measure_time(fib_recursive, n)
        print(string.format("递归版本: 结果 = %d, 耗时 = %.6f 秒", rec_result, rec_time))
        if iter_time > 0 then
            print(string.format("迭代版本比递归版本快 %.2f 倍", rec_time / iter_time))
        end
    else
        print("递归版本对于 n > 30 可能会非常慢，已跳过测试")
    end
    
    print("\n测试完成！")
end

-- 运行测试，计算第30个斐波那契数
run_performance_test(30)

